# DFS 求解迷宫最短路径

# 迷宫: 1 表示障碍，0 表示可走
maze = [
    [1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
    [1, 0, 0, 1, 0, 0, 0, 1, 0, 1],
    [1, 0, 0, 1, 0, 0, 0, 1, 0, 1],
    [1, 0, 0, 0, 0, 1, 1, 0, 0, 1],
    [1, 0, 1, 1, 1, 0, 0, 0, 0, 1],
    [1, 0, 0, 0, 1, 0, 0, 0, 0, 1],
    [1, 0, 1, 0, 0, 0, 1, 0, 0, 1],
    [1, 0, 1, 1, 1, 0, 1, 1, 0, 1],
    [1, 1, 0, 0, 0, 0, 0, 0, 0, 1],
    [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
]
dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)]  # 下一步走的四个方向
visited = []  # 放置已经访问过的方块
min_length = 100000
min_path = []
step = 0  # 试探的总步数
path = []


def DFS(x0, y0, x1, y1):    # 起点(x0,y0) 终点(x1,y1)
    global min_length, min_path, step  # 全局变量: 最短路径长度、存放最短路径、总试探步数
    visited.append((x0, y0))  # 将当前方块置为已访问，并加入path中,试探步数+1
    path.append((x0, y0))
    step = step + 1

    if (x0, y0) == (x1, y1):  # 如果到达终点，当前路径长度与最短路径长度比较
        if min_length > len(path):
            min_path.clear()
            min_path = path.copy()  # 使用copy()复制
            min_length = len(path)
        return

    for dir in dirs:
        tx = x0 + dir[0]
        ty = y0 + dir[1]
        if 0 < tx < 9 and 0 < ty < 9 and maze[tx][ty] == 0 and (tx, ty) not in visited:
            DFS(tx, ty, x1, y1)  # 递归调用
            visited.remove((tx, ty))  # 回溯
            path.pop()


DFS(1, 1, 8, 8)
print(f'BFS 得最短路径如下: ')
for i in min_path:
    if i != (8, 8):
        print(f'{i} → ', end='')
print(f'{(8, 8)}')
print(f'长度为 {len(min_path)}, 总试探步数 {step}')
